#include <stdlib.h>
#include <stdio.h>

int strlen(char* s)
{
  int i;
  for(i=0; *s != '\0'; ++s, ++i);
  return i;
}

void __compute_pre(char* s,int p[],int m)
{
  int k,j;
  p[0] = -1;
  k = -1;
  for(j=1; j<m; ++j){
    while(k>=0 && s[k+1]!=s[j])
      k = p[k];
    if(s[k+1] == s[j])
      ++k;
    p[j] = k;
  }
}
//return the index of the in the string to be searched
int kmp(char* s0, char* s1)
{
  int n,m,i,j;
  n = strlen(s0);
  m = strlen(s1);
  if(m==0)return 0;//empty string
  int* p = (int*)malloc(m*sizeof(int));
  if(p == NULL)
    puts("fail to malloc");

  __compute_pre(s1,p,m);

  j = -1;
  for(i = 0; i<n; ++i){
    while(j>=0 && s1[j+1]!=s0[i])
      j = p[j];
    if(s1[j+1]==s0[i])
      ++j;
    if(j==m-1)
      return i-j;//matched
  }
  return -1;//no match
}

int main()
{
  char* s0 = "abcdefg";
  char* s1 = "cde";
  char* s2 = "";
  printf("%d\n",kmp(s0,s1));
  printf("%d\n",kmp(s0,s2));

  return 0;
}


int test_compute_pre()
{
  char* s1="ababaca";
  int m = strlen(s1);
  int* p = (int*)malloc(m*sizeof(int));
  if(p == NULL)
    puts("fail to malloc");
  int i;
  __compute_pre(s1,p,m);

  for(i=0; i<m; ++i)
    printf("%d\t",p[i]);
  puts("");

  free(p);
  return 0;
}
